class Solution:
    def maximumSwap(self, num: int) -> int:
        if num < 12:
            return num
        arr = []            # 存储数位的栈
        stack = []          # 存储当前最大值索引的栈
        while num != 0:
            r = num%10
            arr.append(r)
            if not stack:
                stack.append(0)
            else:
                if r > arr[stack[-1]]:
                    stack.append(len(arr)-1)
                else:
                    stack.append(stack[-1])
            num = num // 10
        
        n = len(stack)-1
        while n>=0:
            t = stack.pop()
            if arr[t] != arr[n]:        # 从左到右第一位数字，其右边有比它大的数字
                arr[n], arr[t] = arr[t], arr[n]
                break
            n -= 1
        
        
        res = int(''.join(arr[::-1]))
        
        return res

    def maximumSwap(self, num: int) -> int:

        n = list(str(num))

        lg = len(n)

        l = r = p = lg - 1

        for i in range(lg - 2, -1, -1):

            if n[i] > n[p]:

                p = i

            elif n[i] < n[p]:

                l, r = i, p

        n[l], n[r] = n[r], n[l]

        return int(''.join(n))

    """ 作者：清风Python
    链接：https://leetcode.cn/problems/maximum-swap/solutions/1821049/by-qingfengpython-yjti/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。 """